package hero.mps.leet_code_22;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    List<String> combinations = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        // 调用回溯函数开始生成括号组合
        backtrack("", 0, 0, n);
        // 返回生成的括号组合列表
        return combinations;
    }
    private void backtrack(String current, int open, int close, int max) {
        // 如果当前字符串长度等于最大括号数的两倍，说明已经生成了一个完整的括号组合
        if (current.length() == 2*max) {
            // 将当前括号组合添加到结果列表中
            combinations.add(current);
            return;
        }
        // 如果左括号数量小于最大括号数
        if (open < max) {
            // 递归调用回溯函数，添加左括号，并更新左括号和右括号的数量
            backtrack(current + "(", open + 1, close, max);
        }
        // 如果右括号数量小于左括号数量
        if (close < open) {
            // 递归调用回溯函数，添加右括号，并更新左括号和右括号的数量
            backtrack(current + ")", open, close + 1, max);
        }
    }

    public void OptimizedBacktrack(String current, int open, int close, int max){
        if (close > open) return;
        // 如果当前字符串长度等于最大括号数的两倍，说明已经生成了一个完整的括号组合
        if (current.length() == 2*max) {
            // 将当前括号组合添加到结果列表中
            combinations.add(current);
            return;
        }
        // 如果左括号数量小于最大括号数
        if (open < max) {
            // 递归调用回溯函数，添加左括号，并更新左括号和右括号的数量
            backtrack(current + "(", open + 1, close, max);
        }
        // 如果右括号数量小于左括号数量
        if (close < open) {
            // 递归调用回溯函数，添加右括号，并更新左括号和右括号的数量
            backtrack(current + ")", open, close + 1, max);
        }
    }

    public static void main(String[] args) {
        GenerateParentheses g = new GenerateParentheses();
        System.out.println(g.generateParenthesis(3));
    }
}
